#include <mpi.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <omp.h>
#include "fun_group.h"

#define TRUE 1
#define SIZE 100000

double all_start_time, all_end_time, end_time, start_time;

/**
 * 函数名：Partition
 * 功能：给定一个数组，并给定起始和结束坐标，以最后一个元素为基准元素把
 *  较小的数放到左边，较大的数放到右边。并返回交换数据的次数
 * 输入：待分数组data，起始坐标sort_start，终止坐标sort_end
 * 输出：分类完的数组，返回分类中心坐标
*/
int Partition(int *data, int sort_start, int sort_end)
{
    int darum_element;
    darum_element = data[sort_end];
    int i = sort_start - 1; 
    for (int j = sort_start; j < sort_end; ++j)
        if (data[j] <= darum_element)
        {
            i++; // i表示比darum_element小的元素的个数 
            swap(&data[i], &data[j]);
        }
    swap(&data[i + 1], &data[sort_end]);  // 以darum_element为分界，data[i+1]=darum_element
    return i + 1;
}

/**
 * 函数名：QuickSort
 * 功能：当可用处理器只有一个的时候，使用这个函数排序
 * 输入：待排数组 *data, 排序起始位置 sort_start, 排序结束位置 sort_end
 * 输出：有序数组
*/
void QuickSort(int *data, int sort_start, int sort_end)
{
    int dar_ele, i;
    if (sort_start < sort_end)
    {
        dar_ele = Partition(data, sort_start, sort_end);
        QuickSort(data, sort_start, dar_ele - 1);
        QuickSort(data, dar_ele + 1, sort_end);
    }
}

// 功能：求2的number次幂
int exp2(int number)
{
    int res = 1;
    while (number > 0)
        number--, res *= 2;
    return res;
}

// 功能：求以2为底的number的对数
int log2(int number)
{
    int res = 1, j = 2;
    while (j < number)
        j *= 2, res++;
    if (j > number)
        res--;
    return res;
}

/**
 * 函数名: para_QuickSort
 * 功能：并行快速排序，对起止位置为sort_start和sort_end的序列，使用2的p_id次幂个处理器进行排序
 * 输入：无序数组data[1,n]，使用的处理器个数2^p_id
 * 输出：有序数组data[1,n]
 */
void para_QuickSort(int *data, int sort_start, int sort_end, int p_id, int id, int my_rank)
{
    int i, j;
    int dar_ele, MyLength, *temp;
    MPI_Status status;
    MyLength = -1;
    all_start_time = omp_get_wtime();
    // 如果可供选择的处理器只有一个，那么由处理器id调用串行排序
    if (p_id == 0)
    {
        if (my_rank == id)
            QuickSort(data, sort_start, sort_end);
        return;
    }
    // 由第id号处理器划分数据，并将后一部分数据发送到处理器id+exp2(p_id-1)，对应于算法步骤(1.2,1.3)
    if (my_rank == id)
    {
        //将当前的无序区R[1，n]划分成左右两个无序的子区R[1，i-1]和R[i，n](1≤i≤n)
        dar_ele = Partition(data, sort_start, sort_end); // 返回基准元素的位置
        MyLength = sort_end - dar_ele;
        /*(1.3) Pid ssort_end data[dar_ele+1,p_id-1] to P(id+2m-1) 
         {MyLength表示发送缓冲区地址； 发送元素数目为1; my_rank是消息标签 } 
         发送分割数据的基准位置给下一个处理数据的从进程 */
        MPI_Send(&MyLength, 1, MPI_INT, id + exp2(p_id - 1), my_rank, MPI_COMM_WORLD);
        // 若缓冲区不空，则第id+2m-1号处理器取数据的首址是data[dar_ele+1]
        if (MyLength != 0)
            MPI_Send(data + dar_ele + 1, MyLength, MPI_INT, id + exp2(p_id - 1), my_rank, MPI_COMM_WORLD);
    }
    //处理器index+exp2(p_id-1)接受处理器id发送的消息
    if (my_rank == id + exp2(p_id - 1))
    {
        // 接收分基准位置的值
        MPI_Recv(&MyLength, 1, MPI_INT, id, id, MPI_COMM_WORLD, &status);
        if (MyLength != 0)
        {
            temp = (int *)malloc(MyLength * sizeof(int));
            if (temp == 0)
                printf("Malloc memory error!");
            // 接收
            MPI_Recv(temp, MyLength, MPI_INT, id, id, MPI_COMM_WORLD, &status);
        }
    }

    // 用id-1个处理器对sort_start--(dar_ele-1)的数据进行递归排序
    j = dar_ele - 1 - sort_start;
    MPI_Bcast(&j, 1, MPI_INT, id, MPI_COMM_WORLD); // 广播排序信息
    if (j > 0)
        para_QuickSort(data, sort_start, dar_ele - 1, p_id - 1, id, my_rank);
    
    // 用id-1个处理器对(dar_ele+1)--sort_end的数据进行递归排序
    j = MyLength;
    MPI_Bcast(&j, 1, MPI_INT, id, MPI_COMM_WORLD); // 广播排序信息
    if (j > 0)
        para_QuickSort(temp, 0, MyLength - 1, p_id - 1, id + exp2(p_id - 1), my_rank);
    
    // 将排序好的数据由处理器id+exp2(p_id-1)发回id号处理器
    if ((my_rank == id + exp2(p_id - 1)) && (MyLength != 0))
        MPI_Send(temp, MyLength, MPI_INT, id, id + exp2(p_id - 1), MPI_COMM_WORLD);
    if ((my_rank == id) && (MyLength != 0))
        MPI_Recv(data + dar_ele + 1, MyLength, MPI_INT, id + exp2(p_id - 1), id + exp2(p_id - 1), MPI_COMM_WORLD, &status);
}


int main(int argc, char *argv[])
{
    int DataSize = 1e7;
    int *data, *data_1;
    int my_rank, size_all;
    int p_id;
    MPI_Status status;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size_all);

    if (my_rank == 0) {
        //主进程初始化数据
        // scanf("%d", &DataSize);
        data = (int *)malloc(DataSize * sizeof(int));
        data_1 = (int *)malloc(DataSize * sizeof(int));
        CreateData(data, DataSize);
        for (int i = 0; i < DataSize; ++i)
            data_1[i] = data[i];
    }
    p_id = log2(size_all);
    /* 从主进程将数据序列广播到从进程 {"1"表示传送的输入缓冲中的元素的个数, 
     "MPI_INT"表示输入元素的类型, "0"表示root processor的ID } */
    MPI_Bcast(&data, 1, MPI_INT, 0, MPI_COMM_WORLD);
    //ID号为0的处理器调度执行排序
    para_QuickSort(data, 0, DataSize - 1, p_id, 0, my_rank);
    
    all_end_time = omp_get_wtime();

    MPI_Finalize(); // 结束计算
    if (my_rank == 0)
    {
        printf("排序后的有序数组为 :\n");
        for (int i = 0; i < DataSize; i++)
            if (i < 100)
                printf("%d ", data[i]);
        printf("... ...\n");

        /*计算串行时间*/
        start_time = omp_get_wtime();
        serial_QuickSort(data_1, 0, DataSize - 1);
        end_time = omp_get_wtime();

        char sort_name[] = "mpi_quikesort";
		char filepath[] = "result_quick_mpi.txt";
		put_time_info(filepath, sort_name, DataSize, size_all, all_start_time, all_end_time, start_time, end_time);

    }
    return 0;
}
